【动态规划】爬楼梯问题

一个人爬楼梯，每次只能爬1个或两个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法

如果n==1，显然只有从0->1一种方法f(1)=1； 如果n==2，那么有0->1->2、0->2两种方法f(2)=2; 如果n==3,那么可以先爬到第1阶，然后爬两个台阶，或者先爬到第二阶，然后爬一个台阶，显然f(3)=f(2)+f(1); …… 推广到一般情况，对于n(n>=3)个台阶,可以先爬到第n-1个台阶，然后再爬一个台阶，或者先爬到n-2个台阶，然后爬2个台阶，因此有f(n)=f(n-1)+f(n-2)。 那么动态规划的递推公式和边界条件都有了，即：

根据递推公式，可以写如下代码轻松解决问题:

注意：fun（80）的结果非常大，程序运行时间很长，测试的时候可以用小一点的数字测试。 虽然代码简单，但是显然这种方法实在是太耗时间了，递归函数多次重复计算中间结果。我们改进以下，开一个数组来保存中间结果。